package org.hot100_5.leetcode322;

import java.util.Arrays;

public class Solution {
    public int coinChange(int[] coins, int amount) {

        int n = coins.length;
        Arrays.sort(coins);

        int [] dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;

        //完全背包，先物品再容量
        for (int i = 0; i <n; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (dp[j-coins[i]]!=Integer.MAX_VALUE){
                    dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }

        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount] ;
    }
}
